from collections import deque


def IsReachable(road_map, initial, goal):
    'Simple DFS'
    links = road_map.global_links
    visited = set([initial])
    d = deque([initial])
    while d:
        this = d.pop()
        if this == goal:
            return True
        f = links[this]
        d.extend(f - visited)
        visited.update(f)
    return False


def GenerateProblemSet(road_map, k=100):
    '''You must implement this method.
    This method returns a list of (initial,goal) tuples such that initial is
    reachable from goal and vice-versa. k is the total amount of pairs to add.
    Pairs must be chosen randomly. '''
    road_map.global_links = [{x.target for x in j.links}
                             for j in road_map.junctions]

    def reach(s, t):
        return IsReachable(road_map, s, t)

    def get_pair():
        while True:
            s, t = road_map.GenerateProblem()
            if not reach(s, t) or not reach(t, s):
                return (s, t)
    try:
        return [get_pair() for _ in xrange(k)]
    finally:
        del road_map.global_links


def SaveToFile(filename, problem_set):
    '''saves your Problem set to a CSV file.
    The format is <pair i initial>, <pair i goal>'''
    file_ptr = open(filename, 'w')
    for pair in problem_set:
        file_ptr.write(str(pair[0]) + ',' + str(pair[1]) + '\n')
    file_ptr.close()

